package lj.leetcode.code146;

import java.util.Deque;
import java.util.HashMap;
import java.util.LinkedList;
import java.util.Map;

public class LRUCache {
    private Map<Integer, Integer> map;

    private Deque<Integer> deque ;

    private final int capacity ;

    public LRUCache(int capacity) {
        this.map = new HashMap<>(capacity);
        this.deque = new LinkedList<>();
        this.capacity = capacity;
    }

    public int get(int key) {
        if(map.get(key) == null){
            return -1;
        }
        else {
            deque.remove(key);
            deque.addFirst(key);
            return map.get(key);
        }
    }

    public void put(int key, int value) {
        if(map.containsKey(key)){
            deque.remove(key);
            deque.addFirst(key);
        }
        else {
            if(map.size() < capacity){
                deque.addFirst(key);
            }
            else {
                int last = deque.removeLast();
                map.remove(last);
                deque.addFirst(key);
            }
        }
        map.put(key,value);
    }
}
